// 41. 缺失的第一个正数
// 困难
// 相关标签
// 相关企业
// 提示
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 示例 1：
// 输入：nums = [1,2,0]
// 输出：3
// 解释：范围 [1,2] 中的数字都在数组中。
// 示例 2：
// 输入：nums = [3,4,-1,1]
// 输出：2
// 解释：1 在数组中，但 2 没有。
// 示例 3：
// 输入：nums = [7,8,9,11,12]
// 输出：1
// 解释：最小的正数 1 没有出现。

const nums = [3,4,-1,1]
//const nums = [1,2,0]
//const nums = [7,8,9,11,12]

function firstMissingPositive(nums) {
    const n = nums.length;
    // 第一步：将每个正整数 x 放到索引为 x - 1 的位置
    for (let i = 0; i < n; i++) {
        while (
            nums[i] >= 1 &&
            nums[i] <= n &&
            nums[nums[i] - 1] !== nums[i]
        ) {
            // 交换 nums[i] 和 nums[nums[i] - 1]
            const temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    console.log(nums,'调整后');
    // 第二步：找到第一个 nums[i] 不等于 i + 1 的位置
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    // 如果数组中所有位置都满足 nums[i] === i + 1，返回 n + 1
    return n + 1;
}
console.log(firstMissingPositive(nums))